# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

"""
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def height(root: TreeNode) -> int:
            if not root:
                return 0
            leftHeight = height(root.left)
            rightHeight = height(root.right)
            if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:
                return -1 # -1表示不平衡
            else:
                return max(leftHeight, rightHeight) + 1

        return height(root) >= 0

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/solution/ping-heng-er-cha-shu-by-leetcode-solutio-6r1g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""


class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def B(node):
            if node is None:
                return True, 0
            # 左子树或右子树某个不平衡，或者左右深度差大于1，则返回假
            l = B(node.left)
            if not l[0]:
                return False, l[1]+1
            r = B(node.right)
            if not r[0]:
                return False, r[1]+1
            if abs(l[1]-r[1]) > 1:
                return False, max(l[1], r[1])+1
            return True, max(l[1], r[1])+1
        
        return B(root)[0]